import java.util.Stack;

//力扣416. 分割等和子集
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num : nums){
            sum+=num;
        }
        if(sum%2==1){
            return false;
        }
        int target = sum/2;
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
        //dp 代表着在这个循环中循环到某一层此时已经有了哪些和(也就是i)
        for(int num : nums){
            //如果已经有了和为target那么直接返回true即可，提前退出节省时间
            if(dp[target]){
                return true;
            }
            for(int i = target;i>=num;i--){
                dp[i] = dp[i] || dp[i-num];
            }
        }
        return dp[target];
    }
}


//力扣32. 最长有效括号
class Solution2 {
    public int longestValidParentheses(String s) {
        //使用Integer是为了方便记录最长子串的长度
        Stack<Integer> stack = new Stack<>();
        int maxLen = 0;
        stack.push(-1);

        char[] ch = s.toCharArray();
        for(int i=0;i<ch.length;i++){
            if(ch[i]=='('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){ //避免遇到栈中没有'('的情况
                    stack.push(i);
                }else{
                    maxLen = Math.max(maxLen,i-stack.peek());
                }
            }
        }
        return maxLen;
    }
}
//方法二(动态规划):
class Solution3 {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        int[] dp = new int[s.length()];

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i-1) == '(') {
                    // 情况：...()
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                } else {
                    // 情况：...))
                    int prevLen = dp[i-1];
                    int openingPos = i - prevLen - 1;
                    if (openingPos >= 0 && s.charAt(openingPos) == '(') {
                        dp[i] = dp[i-1] + 2 + (openingPos >= 1 ? dp[openingPos-1] : 0);
                    }
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }

        return maxLen;
    }
}